#ifndef _BUILD_DFA_TAB_IMPL
#define _BUILD_DFA_TAB_IMPL

#include "Dfa_base_loc.h"

// build a dfa table from follow value and char set
namespace build_dfa_tab_loc {
	struct Move {		// to denote one move
		char val;			// the move value
		int state;			// go to which state
		Move(char c, int state_num) { val=c; state=state_num; }
	};
	typedef mylib::Set<int> State;		// the state
}
#include <map>
#include <stack>
#include <list>

using namespace mylib;
using namespace dfa_base_str;

Lim_matrix<dfa_base::Dfa_base::State_type> &dfa_base_loc::build_dfa_tab(Set<dfa_base::Dfa_base::State_type> &acc,const Fol_val &fols, const Set<char> &char_set, const Pos_set &first){
	using namespace std;
	using namespace build_dfa_tab_loc;
	map<State, int> states;			// state and state number, to save the exist set
	map<int, list<Move> > list_tab;		// the list form for dfa table
	stack<State> dstate;			// uncalculated state
	int state_num=1;				// to count the state number, initialize it to one just for 0 label not exist
	
	dstate.push(first);				// the initialize as first(root)
	list_tab[state_num];
	states[first] = state_num++;	// set the calculate number
	while( !dstate.empty() ) {
		State cur_state = dstate.top();
		dstate.pop();
		int &cur_state_num=states[cur_state];
		for(mylib::Set<char>::const_iterator C=char_set.begin(); C!=char_set.end(); C++ ) {
			char c = *C;				// for each character
			State new_state;				// the new state for
			for(State::const_iterator S=cur_state.begin(); S!=cur_state.end(); S++ ) { // for each position in state
				int p = *S;		// get the position
				const mylib::Set<char> *ele;
				dfa_base_str::Lex_oper *reg = fols[p].oper;
				if( Reg_base *base = dynamic_cast<Reg_base *>(reg) ) {		// get the elements
					ele = &base->element();
				} else if( End_mark *end = dynamic_cast<End_mark *> (reg) ) {// current state number is accepting state
					acc.insert(cur_state_num-1);
					continue;				// to calculate the next position
				}
				else 
					throw dfa_base::Dfa_base::Err_input();
				if( ele->exist(c) ) {		// can move
					new_state += fols[p].pos_set;		// add follow(p) to new state
				}
			}
			if( !new_state.size() )		// empty
				continue;
			int &num = states[new_state];
			if( !num )	{		// not exist
				num = state_num++;				// add it
				dstate.push(new_state);			// add it to uncalculated state set
				list_tab[cur_state_num].push_back(Move(c, num));
			} else {
				list_tab[cur_state_num].push_back(Move(c, num));	// dstate[cur_state] = {c, to_state]
			}
		}
	}
	int row = states.size();
	int col = char_set.upper()-char_set.low()+1;
	try {
		mylib::Lim_matrix<int> *tab = new mylib::Lim_matrix<int>(row, col, char_set.low(), dfa_base::Err);
		for(map<int, list<Move> >::const_iterator S=list_tab.begin(); S!=list_tab.end(); S++ ) {
			int state = S->first-1;				// since it set from 1
			const list<Move> &moves = S->second;
			for(list<Move>::const_iterator M=moves.begin(); M!=moves.end(); M++ ) {		// for each move
				tab->put(state, M->val, M->state-1);			// set tab[state][char] = state
			}
		}
		return *tab;
	} catch(...) {
		throw dfa_base::Dfa_base::Out_of_mem();
	}
}
#endif